public class Solution01{
	public int findBottomLeftValue(TreeNode root){
		//一个队列解决问题
		Queue<TreeNode> curNodes = new LinkedList<>();
		//当前层节点数
		int curNodeNum = 0;
		//下一层的节点数
		int nextNodeNum = 0;
		//判断是否是该层第一个节点
		boolean isFirst = true;
		int leftValue;

		if(root != null){
			curNodes.offer(root);
			curNodeNum++;
		}
		while(!curNodes.isEmpty()){
			TreeNode curNode = curNodes.poll();
			curNodeNum--;
			if(isFirst){
				leftValue = curNode.val;
				isFirst = false;
			}
			if(curNode.left != null){
				curNodes.offer(curNode.left);
				nextNodeNum++;
			}
			if(curNode.right != null){
				curNodes.offer(curNode.right);
				nextNodeNum++;
			}
			if(curNodeNum == 0){
				if(nextNodeNum == 0){
					break;
				} else {
					isFirst = true;
					curNodeNum = nextNodeNum;
					nextNodeNum = 0;
				}
			}
		}

		return leftValue;
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(){}
	TreeNode(int val){ this.val = val; }
	TreeNode(int val, TreeNode left, TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}
